package ej2;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Vector;

import sun.font.EAttribute;

public class Exacto {
	
	private Integer CANT_NODOS;
	private Integer NODO_COMUN;
	public ArrayList<Integer> enes = new ArrayList<Integer>();
	public Long cantOp = 0L;
	
	private ArrayList<Integer> circuito1 = new ArrayList<Integer>();
	private ArrayList<Integer> circuito2 = new ArrayList<Integer>();
	private Integer[][] pesoEjes;
	
	private int pesoCircuito1;// = pesoCircuito(circuito1);
	private int pesoCircuito2;// = pesoCircuito(circuito2);
	
	public void mostrarPesoEjes()
	{		
		System.out.println("Peso de los ejes del grafo");
		int cantFilas = pesoEjes.length;
		int cantColumnas = 0;
		for(int i = 0; i < cantFilas; i++)
		{
			cantColumnas = pesoEjes[i].length;
			for(int j = 0; j< cantColumnas; j++)
			{
				if(j == (cantColumnas - 1))
					System.out.println(pesoEjes[i][j]);
				else
					System.out.print(pesoEjes[i][j] + " ");
				
			}
		}
	}
/******************  Interfaz *******************************/
	public void setN(Integer n){
		CANT_NODOS = n;
	}
	
	public void setNodoV(Integer n){
		NODO_COMUN = n-1;
	}
	
	public Integer getNodoV() {
		return NODO_COMUN;
	}

	public ArrayList<Integer> getCircuito1() {
		return circuito1;
	}

	public void setCircuito1(ArrayList<Integer> circuito1) {
		this.circuito1 = circuito1;
	}

	public ArrayList<Integer> getCircuito2() {
		return circuito2;
	}

	public void setCircuito2(ArrayList<Integer> circuito2) {
		this.circuito2 = circuito2;
	}

	public Integer getN() {
		return CANT_NODOS;
	}


	public Integer[][] getPesoEjes() {
		return pesoEjes;
	}

	public void setPesoEjes(Integer[][] pesoEjes) {
		this.pesoEjes = pesoEjes;
	}
	
	
/***************************************************/
	
	
	public void exacto() {
		int[] permInicial = new int[CANT_NODOS-1];
		int j = 0;
		circuito1.add(new Integer(getNodoV()));
		circuito2.add(new Integer(getNodoV()));	
		ArrayList<Integer> inicial = new ArrayList<Integer>();
		
		
		for(int i = 0; i < CANT_NODOS-1;i++) {
			if(i != getNodoV()){
				inicial.add(new Integer(j));
				circuito1.add(new Integer(j));
			}
			else{
				j++;
				inicial.add(new Integer(j));
				circuito1.add(new Integer(j));
			}
		j++;
		cantOp++;
		}
		System.out.println(inicial);
		this.pesoCircuito1 = this.pesoCircuito(circuito1);
		this.pesoCircuito2 = this.pesoCircuito(circuito2);
		

		genPerm(inicial);
	}

	public Integer longitud(Integer a, Integer b)
	{
		if(a.equals(b)) {
			System.out.println("ALGOOOOOO ESTAAAA MAAAAL!!!!!!!");
			return(Integer.MIN_VALUE);
		}
		if(a < b) 
			return new Integer(pesoEjes[a][b-1-a]);
		else
			return new Integer(pesoEjes[b][a-1-b]);
	}
	
//	suma todos los pesos de los ejes, que va consultando en pesoEjes de a pares de nodos 
	public int pesoCircuito (ArrayList<Integer> circuito)
	{	
		int peso = 0;
		Integer nodoIni;		
		Integer nodoFin;		
		int cantNodosCirc = circuito.size();	
		int i;
		
		//recorre el circuito, y va sumando el peso del eje actual  
		for(i = 0; i < cantNodosCirc - 1; i++)
		{		
			nodoIni = circuito.get(i);
			nodoFin = circuito.get(i + 1);	
			peso+=longitud(nodoIni, nodoFin);
			cantOp++;					
		}
		
		if(i > 0)
			peso+=longitud(circuito.get(i), circuito.get(0));
		
		return peso;
	}	
	/*
	private void genTodasLasPermut(int[] vector)
	{
		int[] usados = new int[vector.length];
		for (int i = 0; i < usados.length; i++)
		{
			cantOp++;
			usados[i] = 0;
		}
		genPerm(new ArrayList<Integer>(), usados);
	}
*/
	private void genPerm(ArrayList<Integer> solucionActual) 
	{

		int nodoCorte = -1;
		Integer diferenciaMax = 0;
				for(int i = 0; i < solucionActual.size()-1; i++) // itera n-1 veces y busca el nodo de corte
				{	
					cantOp++;
					Integer pesoAristaActual = longitud(solucionActual.get(i), solucionActual.get(i + 1));
					Integer pesoAristaIaNodoV = longitud(solucionActual.get(i),NODO_COMUN);
					Integer pesoAristaImas1ANodoV = longitud(solucionActual.get(i + 1),NODO_COMUN);				
					cantOp++;
														
					if((pesoAristaActual > pesoAristaIaNodoV + pesoAristaImas1ANodoV) && 
					   (pesoAristaActual - pesoAristaIaNodoV - pesoAristaImas1ANodoV) > diferenciaMax)
					{				
						nodoCorte = i+1;					
						diferenciaMax = pesoAristaActual - pesoAristaIaNodoV - pesoAristaImas1ANodoV;					
					}				
				}
			if (nodoCorte == -1) // no hay un corte que favorece a la solucion
			{
solucionActual.add(0,NODO_COMUN); // agrego para tener el circuito a partir del nodoV
System.out.println("agrego :" +solucionActual);
				if(pesoCircuito(solucionActual)<(pesoCircuito1+pesoCircuito2)) //chequeo si es mejor que mi mejor sol anterior
				{	

					circuito1 = (ArrayList<Integer>) solucionActual.clone();
					circuito2.clear();
					circuito2.add(NODO_COMUN);
					pesoCircuito1 = (pesoCircuito(circuito1));
					pesoCircuito2 = (pesoCircuito(circuito2));
				}

				solucionActual.remove(0);
				System.out.println("Remuevo :" +solucionActual);
			}
			else // hay un corte que favorece a la solucion
			{				
				ArrayList<Integer> c2Aux = new ArrayList<Integer>();
				ArrayList<Integer> c1Aux = new ArrayList<Integer>();
				
				c1Aux = (ArrayList<Integer>) solucionActual.clone();
				c1Aux.add(0,NODO_COMUN);
				
				nodoCorte++; // sumo 1 porque agregue el nodo_comun
				c2Aux.add(NODO_COMUN);
				
				for(int i = nodoCorte; i < c1Aux.size(); i++) // divido en 2 circuitos
				{
					c2Aux.add(c1Aux.get(nodoCorte));
					c1Aux.remove(nodoCorte);					
					cantOp++;
				}

				if((pesoCircuito(c1Aux)+pesoCircuito(c2Aux))<(pesoCircuito1+pesoCircuito2))
				{
   
					circuito1.clear();
					circuito2.clear();
					circuito1 = c1Aux;
					circuito2 = c2Aux;				
/*
					for(Integer nodo : solucionActual)
					{
						circuito1.add(new Integer(nodo));
						cantOp++;
					}
					*/
					pesoCircuito1 = (pesoCircuito(circuito1));
					pesoCircuito2 = (pesoCircuito(circuito2));						
				}

	//			solucionActual.remove(0);
	//			System.out.println("Remuevo :" +solucionActual);
			}
		
	
		// me fijo si todavia me faltan calcular permutaciones
		
			System.out.println(solucionActual);
		while(next_perm(solucionActual)){
			System.out.println(solucionActual);
			nodoCorte = -1;
			diferenciaMax = 0;
					for(int i = 0; i < solucionActual.size()-1; i++) // itera n-1 veces y busca el nodo de corte
					{	
						cantOp++;
						Integer pesoAristaActual = longitud(solucionActual.get(i), solucionActual.get(i + 1));
						Integer pesoAristaIaNodoV = longitud(solucionActual.get(i),NODO_COMUN);
						Integer pesoAristaImas1ANodoV = longitud(solucionActual.get(i + 1),NODO_COMUN);				
						cantOp++;
															
						if((pesoAristaActual > pesoAristaIaNodoV + pesoAristaImas1ANodoV) && 
						   (pesoAristaActual - pesoAristaIaNodoV - pesoAristaImas1ANodoV) > diferenciaMax)
						{				
							nodoCorte = i+1;					
							diferenciaMax = pesoAristaActual - pesoAristaIaNodoV - pesoAristaImas1ANodoV;					
						}				
					}
				if (nodoCorte == -1)
				{
	solucionActual.add(0,NODO_COMUN);
	System.out.println("agrego :" +solucionActual);
					if(pesoCircuito(solucionActual)<(pesoCircuito1+pesoCircuito2)) //chequeo si es mejor que mi mejor sol anterior
					{		    
						circuito1 = (ArrayList<Integer>) solucionActual.clone();
						circuito2.clear();
						circuito2.add(NODO_COMUN);
						pesoCircuito1 = (pesoCircuito(circuito1));
						pesoCircuito2 = (pesoCircuito(circuito2));
					}

					solucionActual.remove(0);
					System.out.println("Remuevo :" +solucionActual);
				}
				else
				{				

					ArrayList<Integer> c2Aux = new ArrayList<Integer>();
					ArrayList<Integer> c1Aux = new ArrayList<Integer>();
				
					c1Aux = (ArrayList<Integer>) solucionActual.clone();
					c1Aux.add(0,NODO_COMUN);
		
					nodoCorte++;
					c2Aux.add(NODO_COMUN);
					
					for(int i = nodoCorte; i < c1Aux.size(); i++) // divido en 2 circuitos
					{
						c2Aux.add(c1Aux.get(nodoCorte));
						c1Aux.remove(nodoCorte);					
						cantOp++;
					}

					if((pesoCircuito(c1Aux)+pesoCircuito(c2Aux))<(pesoCircuito1+pesoCircuito2))
					{
	   
						circuito1.clear();
						circuito2.clear();
						circuito1 = c1Aux;
						circuito2 = c2Aux;				

						pesoCircuito1 = (pesoCircuito(circuito1));
						pesoCircuito2 = (pesoCircuito(circuito2));						
					}

				}
			}
	}	
			

	public static boolean next_perm(ArrayList<Integer> s)
	{
		int i = s.size();
		int j = s.size();
		int n = s.size();
		
		if(n<=1) return false;
		
		// buscar primer par en orden (s[i], s[i+1])
		for(i=n-2; i>=0; i--)
			if (s.get(i) < s.get(i+1)) break;
		
		if (i<0) return false;

		// buscar a la derecha de este par, el menor elemento mayor que s[i]
		for (j=n-1; j>i; j--)
			if (s.get(i) < s.get(j)) break;
		
		swap(i, j,s);
		
		// dar vuelta todo lo que quedo de i+1 en adelante
		for (i++, j=n-1; i<j; i++, j--)
			swap(i, j,s);
		
		return true;
	}


private static void swap(int x, int y, ArrayList<Integer> s) 
{
	Integer tmp = new Integer(s.get(x));
	s.set(x, s.get(y));
	s.set(y, tmp);
}
	
}
